class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int left1 = 0, left2 = 0, n = nums.size(), ans = 0;
        unordered_map<int, int> mm1, mm2;
        for (int right = 0; right < n; right++) {
            mm1[nums[right]]++, mm2[nums[right]]++;
            while (mm1.size() > k) {
                int tmp = nums[left1++];
                if (--mm1[tmp] == 0)
                    mm1.erase(tmp);
            }
            while (mm2.size() >= k) {
                int tmp = nums[left2++];
                if (--mm2[tmp] == 0)
                    mm2.erase(tmp);
            }
            // cout << left1 <<' ' << left2 <<' ' << right << endl;
            ans += left2 - left1;
        }
        return ans;
    }
};
class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int left = 0,right = 0,ans = 0, n = nums.size(),pos = 0;
        for(;right < n;right++){
            while((pos & nums[right]) != 0){
                pos -= nums[left++];
            }
            pos |= nums[right];
            ans = max(ans,right - left + 1);
        }
        return ans;
    }
};
bool fun(unordered_map<int, int>& mm) {
    if (mm.size() == 1)
        return false;
    if (mm.size() > 2)
        return true;
    auto begin = mm.begin(), rbegin = mm.begin();
    rbegin++;

    return (begin->second > 1) && (rbegin->second > 1);
}
class Solution {
public:
    int maxRepOpt1(string text) {
        int left = 0, right = 0, n = text.size(), ans = 0;
        int nums[256] = {0};
        for (auto e : text)
            nums[e]++;
        unordered_map<int, int> mm;
        for (; right < n; right++) {
            mm[text[right]]++;
            while (fun(mm)) {
                int tmp = text[left++];
                if (--mm[tmp] == 0)
                    mm.erase(tmp);
            }
            cout << left << ' ' << right << endl;
            int tmp = right - left + 1;
            if (mm[text[right]] == 1)
                tmp = min(right - left + 1,nums[text[left]]);
            else
                tmp = min(right - left + 1,nums[text[right]]);

            ans = max(ans,tmp);
        }
        return ans;
    }
};
bool fun(map<int, int>& mm, int k, int sum) {
    for (auto& e : mm) {
        if(sum - e.second <= k)
            return false;
    }
    return true;
}
class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0, right = 0, n = s.size(), ans = 0;
        map<int, int> mm;
        for (; right < n; right++) {
            mm[s[right]]++;
            while (right >= left && fun(mm, k, right - left + 1)) {
                char c = s[left++];
                if (--mm[c] == 0)
                    mm.erase(c);
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
vector<int> s_map,p_map;
bool fun(string& s, string& p,int pos){
    for(int i = 0; i < 26;i ++){
        if(s_map[i] != p_map[i])  return false; 
    }
    return true;//p != s.substr(pos,p.size());
}
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        s_map = vector<int>(26);
        p_map = vector<int>(26);
        for(auto e : p)  p_map[e - 'a']++;
        int k = p.size();
        vector<int>ret;
        for(int i = 0;i < s.size();i++){
            s_map[s[i] - 'a']++;
            if(i >= k) s_map[s[i - k] - 'a']--;

            if(s_map[s[i] - 'a'] == p_map[s[i] - 'a'])
            {
                if(fun(s,p,i))   ret.push_back(i - p.size() + 1);
            }
        }
        return ret;
    }
};
typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
public:
    int waysToSplit(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<long long> vv(n + 1);
        for (int i = 0; i < n; i++) {
            vv[i + 1] = vv[i] + nums[i];
        }
        int right1 = 2, right2 = 2;
        vector<long long> s(vv);
        for (int left = 2; left < n; left++) {
            right1 = max(right1, left), right2 = max(right2, left);
            while (right2 + 1 < n &&
                   vv[n] - vv[right2 + 1] >= vv[right2 + 1] - vv[left - 1])
                right2++;
            while (right1 < n && vv[right1] < 2 * vv[left - 1])
                right1++;
            if (right2 < n && right1 <= right2 &&
                vv[right1] - vv[left - 1] >= vv[left - 1] &&
                vv[n] - vv[right2] >= vv[right2] - vv[left - 1])
                ans = (ans + right2 - right1 + 1)%MOD;
        }
        return ans;
    }
};